Due to the difficulty of test pattern generation for sequential circuits, several design-for-testability (DFT) approaches have been proposed. An improvement to these current approaches is needed to cater to the requirements of today's more complicated chips. This paper introduces a new DFT method applicable to high-level description of circuits, which optimally utilizes existing functional elements and paths for test. This technique, called F-scan, effectively reduces the hardware overhead due to test without compromising fault coverage. Test application time is also kept at the minimum. The comparison of F-scan with the performance of gate-level full scan design is shown through the experimental results.

This paper proposes a high-speed architecture to realize two-variable numeric functions. It represents the given function as an edge-valued multiple-valued decision diagram (EVMDD), and shows a systematic design method based on the EVMDD. To achieve a design, we characterize a numeric function f by the values of l and p for which f is an l-restricted Mp-monotone increasing function. Here, l is a measure of subfunctions of f and p is a measure of the rate at which f increases with an increase in the dependent variable. For the special case of an EVMDD, the EVBDD, we show an upper bound on the number of nodes needed to realize an l-restricted Mp-monotone increasing function. Experimental results show that all of the two-variable numeric functions considered in this paper can be converted into an l-restricted Mp-monotone increasing function with p=1 or 3. Thus, they can be compactly realized by EVBDDs. Since EVMDDs have shorter paths and smaller memory size than EVBDDs, EVMDDs can produce fast and compact NFGs.

This paper first reviews the trends of VLSI design, focusing on the power dissipation and programmability. Then, we show the advantage of Quarternary Decision Diagrams (QDDs) in representing and evaluating logic functions. That is, we show how QDDs are used to implement QDD machines, which yield high-speed implementations. We compare QDD machines with binary decision diagram (BDD) machines, and show a speed improvement of 1.28-2.02 times when QDDs are chosen. We consider 1-and 2-address BDD machines, and 3- and 4-address QDD machines, and we show a method to minimize the number of instructions.

Decision diagrams (DDs) are data structures commonly used for representation of discrete functions with large number of variables. Binary DDs (BDDs) are used for representation and manipulation with Boolean functions. Complexity of a BDD is usually measured by its size, that is defined as the number of non-terminal nodes in the BDD. Minimization of the sizes of DDs is a problem greatly considered in literature and many related algorithms (exact and heuristic) have been proposed. However, there are many functions for which BDDs when minimized are still large and can have even an exponential size in the number of variables. An approach to derive compact decision diagram representations for such functions is transformation of BDDs into Multi-valued DDs (MDDs) and Heterogeneous MDDs (HMDDs). Complexity of MDDs and HMDDs is measured by the cost which is a generalization of the notion of the size by taking into account complexity of nodes in MDDs and HMDDs. This paper presents a method for transformation of BDD into HMDD with minimal cost. The proposed method reduces the time for determination of the type of nodes in HMDDs by introducing a matrix expressing dependency (interconnections) among nodes at different levels. Comparing to other methods for conversion of BDDs into HMDDs, the method reduces the number of traverses of a BDD necessary for collecting enough information to construct an equivalent HMDD. For an experimental verification of its efficiency, the method is applied to construction of HMDDs for some benchmark functions and their arithmetic and Walsh spectra.

In this paper, we introduce a unified framework based on a canonical decision diagram called Horner Expansion Diagram (HED) [1] for the purpose of equivalence checking of datapath oriented hardware designs in various design stages from an algorithmic description to the gate-level implementation. The HED is not only able to represent and manipulate algorithmic specifications in terms of polynomial expressions with modulo equivalence but also express bit level adder (BLA) description of gate-level implementations. Our HED can support modular arithmetic operations over integer rings of the form Z2n. The proposed techniques have successfully been applied to equivalence checking on industrial benchmarks. The experimental results on different applications have shown the significant advantages over existing bit-level and also word-level equivalence checking techniques.

Recently much attention has been paid to quantum circuit design to prepare for the future "quantum computation era." Like the conventional logic synthesis, it should be important to verify and analyze the functionalities of generated quantum circuits. For that purpose, we propose an efficient verification method for quantum circuits under a practical restriction. Thanks to the restriction, we can introduce an efficient verification scheme based on decision diagrams called Decision Diagrams for Matrix Functions (DDMFs). Then, we show analytically the advantages of our approach based on DDMFs over the previous verification techniques. In order to introduce DDMFs, we also introduce new concepts, quantum functions and matrix functions, which may also be interesting and useful on their own for designing quantum circuits.

Synthesis of quantum circuits is essential for building quantum computers. It is important to verify that the circuits designed perform the correct functions. In this paper, we propose an algorithm which can be used to verify the quantum circuits synthesized by any method. The proposed algorithm is based on BDD (Binary Decision Diagram) and is called X-decomposition Quantum Decision Diagram (XQDD). In this method, quantum operations are modeled using a graphic method and the verification process is based on comparing these graphic diagrams. We also develop an algorithm to verify reversible circuits even if they have a different number of garbage qubits. In most cases, the number of nodes used in XQDD is less than that in other representations. In general, the proposed method is more efficient in terms of space and time and can be used to verify many quantum circuits in polynomial time.

A multiple-output function can be represented by a binary decision diagram for characteristic function (BDD_for_CF). This paper presents a method to represent multiple-output incompletely specified functions using BDD_for_CFs. An algorithm to reduce the widths of BDD_for_CFs is presented. This method is useful for decomposition of incompletely specified multiple-output functions. Experimental results for radix converters, adders, a multiplier, and lists of English words show that this method is useful for the synthesis of LUT cascades. An implementation of English words list by LUT cascades and an auxiliary memory is also shown.

Numerical function generators (NFGs) realize arithmetic functions, such as ex,sin(πx), and , in hardware. They are used in applications where high-speed is essential, such as in digital signal or graphics applications. We introduce the edge-valued binary decision diagram (EVBDD) as a means of reducing the delay and memory requirements in NFGs. We also introduce a recursive segmentation algorithm, which divides the domain of the function to be realized into segments, where the given function is realized as a polynomial. This design reduces the size of the multiplier needed and thus reduces delay. It is also shown that an adder can be replaced by a set of 2-input AND gates, further reducing delay. We compare our results to NFGs designed with multi-terminal BDDs (MTBDDs). We show that EVBDDs yield a design that has, on the average, only 39% of the memory and 58% of the delay of NFGs designed using MTBDDs.

SIMD instructions are often implemented in modern multimedia oriented processors. Although SIMD instructions are useful for many digital signal processing applications, most compilers do not exploit SIMD instructions. The difficulty in the utilization of SIMD instructions stems from data parallelism in registers. In assembly code generation, the positions of data in registers must be noted. A technique of generating pack instructions which pack or reorder data in registers is essential for exploitation of SIMD instructions. This paper presents a code generation technique for SIMD instructions with pack instructions. SIMD instructions are generated by finding and grouping the same operations in programs. After the SIMD instruction generation, pack instructions are generated. In the pack instruction generation, Multi-valued Decision Diagram (MDD) is introduced to represent and to manipulate sets of packed data. Experimental results show that the proposed code generation technique can generate assembly code with SIMD and pack instructions performing repacking of 8 packed data in registers for a RISC processor with a dual-issue coprocessor which supports SIMD and pack instructions. The proposed method achieved speedup ratio up to about 8.5 by SIMD instructions and multiple-issue mechanism of the target processor.

Decision diagrams are often used for efficient representation of discrete functions in terms of needed storage space and processing time. In this paper, we propose an XML (Extensible Markup Language) based standard for the structural description of various types of decision diagrams. The proposed standard describes elements of the structure common to various types of decision diagrams. It also provides facilities for storing additional information, specific to particular types of decision diagrams. Properties of XML enable us to define a standard that is flexible enough to be applicable to various existing types of decision diagrams as well as new types that could be defined in the future. The existence of such a standard permits efficient storage and exchange of data in decision diagram form between various software systems. In this way, it supports benchmarking, testing and verification of various procedures using decision diagrams as a basic data structure.

We propose a new method of logic synthesis for dual-rail RSFQ (rapid single-flux-quantum) digital circuits. RSFQ circuit technology is one of the strongest candidates for the next generation technology of digital circuits. For representing logic functions, we use a root-shared binary decision diagram (RSBDD) which is a directed acyclic graph constructed from binary decision diagrams. In the method, first we construct an RSBDD from given logic functions, and then reduce the number of nodes in the constructed RSBDD by variable re-ordering. Finally, we synthesize a dual-rail RSFQ circuit from the reduced RSBDD. We have implemented the method and have synthesized benchmark circuits. We have synthesized dual-rail circuits that consist of about 27% fewer logic elements than those synthesized by a Transduction-based method on average.

This paper outlines the method of constructing single-electron logic circuits based on the binary decision diagram (BDD), a graphical representation of digital functions. The circuit consists of many unit devices, BDD devices, cascaded to build the tree of a BDD graph. Each BDD device corresponds to a node of the BDD graph and operates as a two-way switch for the transport of a single electron. Any combinatorial logic can be implemented using BDD circuits. Several subsystems for a single-electron processor have been constructed using semiconductor nano-process technology.

A new moment computation technique for general lumped R(L)C interconnect circuits with multiple resistor loops is proposed. Using the concept of tearing, a lumped R(L)C network can be partitioned into a spanning tree and several resistor links. The contributions of network moments from each tree and the corresponding links can be determined independently. By combining the conventional moment computation algorithms and the reduced ordered binary decision diagram (ROBDD), the proposed method can compute system moments efficiently. Experimental results have demonstrate that the proposed method can indeed obtain accurate moments and is more efficient than the conventional approach.

A new approach for ultra-low-power LSIs based on quantum devices is presented and its present status and critical issues are discussed with a brief background review on the semiconductor nanotechnology. It is a hexagonal binary decision diagram (BDD) quantum logic circuit approach suitable for realization of ultra-low-power logic/memory circuits to be used in new applications such as intelligent quantum (IQ) chips embedded in the ubiquitous network environment. The basic concept of the approach, circuit examples showing its feasibility, growth of high density nanostructure networks by molecular beam epitaxy (MBE) for future LSI implementation, and the key processing issues including the device isolation issue are addressed.

This paper considers Quasi-Reduced ordered Multi-valued Decision Diagrams with k bits (QRMDD(k)s) to represent binary logic functions. Experimental results show relations between the values of k and the numbers of nodes, the memory sizes, the numbers of memory accesses, and area-time complexity for QRMDD(k). For many benchmark functions, the numbers of nodes and memory accesses for QRMDD(k)s are nearly equal to of the corresponding Quasi-Reduced ordered Binary Decision Diagrams (QRBDDs), and the memory sizes and the area-time complexities for QRMDD(k)s are minimum when k = 2 and k = 3-6, respectively.

A systematic and efficient approach is presented to generating simple yet accurate symbolic expressions for transfer functions and characteristics of large linear analog circuits. The approach is based on a compact determinant decision diagram (DDD) representation of exact transfer functions and characteristics. Several key tasks of generating interpretable symbolic expressions--DDD graph simplification, term de-cancellation, and dominant-term generation--are shown to be able to perform linearly by means of DDD graph operations. An efficient algorithm for generating dominant terms is presented based on the concepts of finding the k-shortest paths in a DDD graph. Experimental results show that our approach outperforms other start-of-the-art approaches, and is capable of generating interpretable expressions for typical analog blocks in minutes on modern computer workstations.

SpecC language is designated to handle the design of entire system from specification to implementation and of hardware/software co-design. Concurrency is one of the features of SpecC which expresses the parallel execution of processes. Describing the systems which contain concurrent behaviors would have some data exchanging or transferring among them. Therefore, the synchronization semantics (notify/wait) of events should be incorporated. The actual design, which is usually sophisticated by its characteristic and functionalities, may contain a bunch of event synchronization codes. This will make the design difficult and time-consuming to verify. In this paper, we introduce a technique which helps verifying the synchronization of events in SpecC. The original SpecC code containing synchronization semantics is parsed and translated into a Boolean SpecC code. The difference decision diagrams (DDDs) is used to verify for event synchronization on Boolean SpecC code. The counter examples for tracing back to the original source are given when the verification results turn out to be unsatisfied. Here we also introduce idea on automatically refinement when the results are unsatisfied and preset some preliminary results.

This paper presents a group theoretic approach to the design of Decision diagrams (DDs) with increased functionality of nodes. Basic characteristics of DDs determine their applications, and thus, the optimization of DDs with respect to different characteristics is an important task. Increased functionality of nodes provides for optimization of DDs. In this paper, the methods for optimization of binary DDs by pairing of variables are interpreted as the optimization of DDs by changing the domain group for the represented functions. Then, it is pointed out that, for Abelian groups, the increased functionality of nodes by using larger subgroups may improve some of the characteristics of DDs at the price of other characteristics. With this motivation, we proposed the use of non-Abelian groups for the domain of represented functions by taking advantages from basic features of their group representations. At the same time, the present methods for optimization of DDs, do not offer any criterion or efficient algorithm to choose among a variety of possible different DDs for an assumed domain group. Therefore, we propose Fourier DDs on non-Abelian groups to exploit the reduced cardinality of the Fourier spectrum on these groups.

A shared binary decision diagram (SBDD) represents a multiple-output function, where nodes are shared among BDDs representing the various outputs. A partitioned SBDD consists of two or more SBDDs that share nodes. The separate SBDDs are optimized independently, often resulting in a reduction in the number of nodes over a single SBDD. We show a method for partitioning a single SBDD into two parts that reduces the node count. Among the benchmark functions tested, a node reduction of up to 23% is realized.